perm filename T.TEX[154,PHY] blob
sn#855630 filedate 1988-04-07 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00008 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00007 00003 \font\rmn=cmr9 %ninepoint
C00010 00004 \newbox\bgcrc \setbox\bgcrc=\hbox{$\bigcirc$}
C00013 00005 \display 20pt:$\bullet$:
C00014 00006 $$\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt
C00015 00007 $$\vbox{\offinterlineskip
C00022 00008 Since $R↓∞=\cup R↓i$, $qR↓∞q'$ iff $(\exists x)(q\delta↓x\in F∧q'\delta↓x\in\bar{F})$,
C00024 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\medskip
\halign{\qquad\qquad #\hfil\cr
$\displaystyle{\left.\eqalign{%
&\!(X↓1\,\vec{\otimes}\, X↓2)\,\vec{\otimes}\, X↓3
=X↓1\,\vec{\otimes}\,(X↓2→X↓3)\cr
&\!(X↓1\cup X↓2)\cup X↓3=X↓1\cup(X↓2\cup X↓3)\cr}
\right\}}$\quad associativity\cr
\noalign{\smallskip}
$X↓1\cup X↓2=X↓2\cup X↓1$\quad commutativity\cr
\noalign{\smallskip}
$\displaystyle{\left.\eqalign{%
&\!\Lambda\,\vec{\otimes}\, X=X\,\vec{\otimes}\,\Lambda\cr
&\!\emptyset\cup X=X=X\cup\emptyset\cr}
\right\}}$\quad identity\cr
\noalign{\smallskip}
$\displaystyle{\left.\eqalign{%
&\!(X↓1\cup X↓2)\,\vec{\otimes}\, Y=
(X↓1\,\vec{\otimes}\, Y)\cup(X↓2\,\vec{\otimes}\, Y)\cr
&\!X\,\vec{\otimes}\, (Y↓1\cup Y↓2)=(X\,\vec{\otimes}\, Y↓1)\cup
(X\,\vec{\otimes}\,Y↓2)\cr}
\right\}}$\quad distributivity\cr
\noalign{\smallskip}
$X↑0=\Lambda$\cr
\noalign{\smallskip}
$X↑{i+1}=X↑i\,\vec{\otimes}\, X$\cr
\noalign{\smallskip}
$X↑{i+j}=X↑i\,\vec{\otimes}\, X↑j$\cr
\noalign{\smallskip}
$X\!\!\uparrow\, =\Lambda\cup X\!\!\uparrow\, \vec{\otimes}\, X$\cr
\noalign{\smallskip}
$X\!\!\uparrow\uparrow\, =X\!\!\uparrow$\cr
\noalign{\smallskip}
$X\!\!\uparrow\,\vec{\otimes}\,X\!\!\uparrow\;=X\!\!\uparrow$\cr}
\bye
\bigskip
$$\vcenter{\halign{%
$\hfil#\hfil$\enspace%arrow
&\hfil#\hfil\qquad%number
&\hfil#\hfil\quad%number
&\hfil#\hfil\qquad%description
&\hfil#\hfil\quad%number
&\hfil#\hfil\quad%description
&\hfil#\hfil\qquad%number
&\hfil#\hfil\quad%description
&\hfil#\hfil%number
&\hfil#\hfil\cr
&&&&&{\tt INCREASE}\cr
&&&{\tt READ}$a$&4&&&{\tt ZERO}&7&$↑+$\cr
\noalign{\bigskip}
&&&&&{\tt EOF}\cr
\Rightarrow&1&2&&&&6\cr
&&&{\tt READ}$b$&&{\tt DECREMENT}&&{\tt NONZERO}&8\cr
&&&&5\cr}}$$
\bigskip
\bigskip
\bigskip
\bigskip
$$\vcenter{\halign{$\hfil#\hfil$\quad&#\hfil&\hfil#\hfil\qquad%
&\hfil#\hfil&\hfil#\hfil\cr
&{\tt READ, INCREASE}\cr
\noalign{\bigskip\bigskip}
&&{\tt EOF, ZERO}\cr
\Rightarrow&2&&7&$↑+$\cr
\noalign{\bigskip\bigskip}
&{\tt READ}$b$, {\tt DECREASE}\cr}}$$
\bye
\font\ms=cmsy7
\def\circ1{{\ooalign
{\hfil\raise.07ex\hbox{1}\hfil\crcr\mathhexbox20D}}}
arrow in \circ1.
\bye
\baselineskip 14pt
\def\dminus{\mathrel{\vbox{\lineskip-1pt\baselineskip0pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
%$$a\dminus x↓{i{\mathchoice{\dminus}}j}\times x↓{i+j}+j$$
$$a\dminus x↓{\mathchoice{i\dminus j}}\times x↓{i+j}+j$$
\bye
\font\rmn=cmr9 %ninepoint
\def\dminus{\mathrel{\vbox{\lineskip0pt\baselineskip0pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
\def\ddminus{\mathrel{\vbox{\lineskip0pt\baselineskip0pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
$$x\dminus y$$
\def\dminus{\mathrel{\vbox{\lineskip-2pt\baselineskip-3pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
$$x\dminus y$$
\def\dminus{\mathrel{\vbox{\lineskip-2pt\baselineskip0pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
$$x\dminus y$$
\def\dminus{\mathrel{\vbox{\lineskip-1pt\baselineskip0pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
$$x\dminus y$$
\bye
$$\vbox{\offinterlineskip
\halign{\hfil$#$\quad
&\hfil$#$\hfil%\vrule
&\quad\hfil$#$\hfil\quad%
&\hfil$#$\hfil%\vrule
&$\;$\hfil$#$\hfil$\;$%
&\hfil$#$\hfil\quad%\vrule
&\hfil$#$\hfil%
&\quad\hfil$#$\hfil%\vrule
&$\;$\hfil$#$\hfil$\;$%
&\hfil$#$\hfil%\vrule
&\quad\hfil$#$\hfil\quad%
&\hfil$#$\hfil\cr%\vrule
&&\multispan4\hfil\hbox{First portion}\hfil&&\multispan5\hfil\hbox{Second
portion}\hfil\cr
\noalign{\smallskip}
&\multispan{10}\downbracefill\downbracefill\cr
\noalign{\medskip}
&&\multispan9\hrulefill\cr
x=&\vrule height12pt depth6pt&x↓1&\vrule height12pt depth6pt&x↓2≠\epsilon%
&\vrule height12pt depth6pt&x↓3&\vrule height12pt depth6pt%
&x↓4&\vrule height12pt depth6pt&x↓5&\vrule height12pt depth6pt\cr
&&\multispan9\hrulefill\cr
\noalign{\medskip}
&&&q↓i&&q↓i&&q↓j&&q↓j\cr
\noalign{\smallskip}
&&\multispan9\hrulefill\cr
y=&\vrule height12pt depth6pt&y↓1&\vrule height12pt depth6pt&y↓2%
&\vrule height12pt depth6pt&y↓3&\vrule height12pt depth6pt&y↓4≠\epsilon%
&\vrule height12pt depth6pt&y↓5&\vrule height12pt depth6pt\cr
&&\multispan9\hrulefill\cr
}}$$
\bye
\newbox\bgcrc \setbox\bgcrc=\hbox{$\bigcirc$}
\def\orightarrow{\mathop{\hbox to 0pt{\kern-.25pt\raise2pt\hbox to 1\wd\bgcrc{\hfil
$\scriptscriptstyle\rightarrow$\hfil}\hss}\bigcirc}}
%\newbox\bgcrc \setbox\bgcrc=\hbox{$\bigcirc$}
%\def\orightarrow{\mathop{\hbox to 0pt{\kern-.5pt\raise1pt\hbox to 1\wd\bgcrc{\hfil
% $\scriptstyle\rightarrow$\hfil}\hss}\bigcirc}}
$$V\orightarrow V$$
\bye
\smallskip
\halign{\qquad\qquad #\hfil\cr
$\!\!\displaystyle{\left.{(X↓1\orightarrow X↓2)\orightarrow X↓3
=X↓1\orightarrow (X↓2→X↓3)\atop
\!\!\!\!\!(X↓1\cup X↓2)\cup X↓3=X↓1\cup(X↓2\cup X↓3)
}\right\}}$
\quad associativity\cr
\noalign{\smallskip}
$X↓1\cup X↓2=X↓2\cup X↓1$\quad commutativity\cr
\noalign{\smallskip}
$\!\!\displaystyle{\left.{\!\!\!\!\!\!\!\!\Lambda\orightarrow X=X\orightarrow\Lambda
%\phantom{(((\emptyset \cup}
\atop
\emptyset\cup X=X=X\cup\emptyset}\right\}}$\quad identity\cr
\noalign{\smallskip}
$\!\!\displaystyle{\left.{(X↓1\cup X↓2)\orightarrow Y=
(X↓1\orightarrow Y)\cup(X↓2\orightarrow Y)
\atop
X\orightarrow (Y↓1\cup Y↓2)=(X\orightarrow Y↓1)\cup (X\orightarrow Y↓2)
\phantom{(\cup}}
\right\}}$\quad distributivity\cr
\noalign{\smallskip}
$X↑0=\Lambda$\cr
\noalign{\smallskip}
$X↑{i+1}=X↑i\orightarrow X$\cr
\noalign{\smallskip}
$X↑{i+j}=X↑i\orightarrow X↑j$\cr
\noalign{\smallskip}
$X\!\!\uparrow\, =\Lambda\cup X\!\!\uparrow \orightarrow X$\cr
\noalign{\smallskip}
$X\!\!\uparrow\uparrow\, =X\!\!\uparrow$\cr}
\bye
\display 20pt:$\bullet$:
$(1<a≤b<n)$
\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt
\vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}
\setbox3=\vbox{\hsize 15pc\noindent\strut
{\bf Heuristic:} change $<$ to $≤$, and $>$ to $≥$
\strut}
\smallskip
\display 20pt::
\boxit{\box3}
\bye
$$\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt
\vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}
\setbox4=\vbox{\hsize 33pc \noindent \strut
{\bf Heuristic:} In summing a rational function like ${2\over (b-a+3)(b-a+2)}$
with a factorable denominator, use partial fractions to get a summand where
all denominators are linear. Here,
$${2\over (b-a+3)(b-a+2)}={2\over b-a+2}-{2\over b-a+3}$$
\strut}
\boxit{\box4}$$
\bye
$$\vbox{\offinterlineskip
\halign{$#$&$#$&$#$&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip
&\hbox{\qquad}$#$\xskip%
&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip\cr
&&y&\omit&&&\pi↓1&&&&&\omit&&&\pi↓2\cr
x&&&\omit&0&1&2&3&4&&&\omit&0&1&2&3&4\cr
&&&\multispan7\hrulefill&&\multispan7\hrulefill\cr
&&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&&\omit&\omit&\omit%
&\omit&\omit&\omit\cr
&0&&&1&3&5&7&9&\ldots&0&&1&4&9&16&\ldots\cr
&1&&&2&6&10&14&18&\ldots&1&&2&3&8&15&\ldots\cr
&2&&&4&12&20&28&36&\ldots&2&&5&6&7&14&\ldots\cr
&3&&&8&24&40&56&\ldots&&3&&10&11&12&13&\ldots\cr
&4&&&16&48&80&\ldots&&&4&&17&18&\ldots\cr
}}$$
$$\vbox{\offinterlineskip
\halign{\hfil$#$\xskip&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip\cr
&\omit&&&\pi↓3\cr
&\omit&0&1&2&3&4\cr
&\multispan7\hrulefill\cr
&height2pt\cr
0&&1&3&6&10&15&\ldots\cr
1&&2&5&9&14&\ldots\cr
2&&4&8&13&\ldots\cr
3&&7&12&18\cr
4&&11&17\cr
5&&16\cr
}}$$
\bye
$$\vbox{\offinterlineskip
\halign{$#$&$#$&$#$&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip
&\hbox{\qquad}$#$\xskip%
&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip
&\hbox{\qquad}$#$\xskip%
&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip\cr
&&y&\omit&&&\pi↓1&&&&&\omit&&&\pi↓2&&&&&\omit&&&\pi↓3\cr
x&&&\omit&0&1&2&3&4&&&\omit&0&1&2&3&4&&\omit&0&1&2&3&4\cr
&&&\multispan7\hrulefill&&\multispan7\hrulefill&&\multispan7\hrulefill\cr
&&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&&\omit&\omit&\omit%
&\omit&\omit&\omit&&\omit&\omit&\omit&\omit&\omit&\omit\cr
&0&&&1&3&5&7&9&\ldots&0&&1&4&9&16&\ldots&0&&1&3&6&10&15&\ldots\cr
&1&&&2&6&10&14&18&\ldots&1&&2&3&8&15&\ldots&1&&2&5&9&14&\ldots\cr
&2&&&4&12&20&28&36&\ldots&2&&5&6&7&14&\ldots&2&&4&8&13&\ldots\cr
&3&&&8&24&40&56&\ldots&&3&&10&11&12&13&\ldots&3&&7&12&18\cr
&4&&&16&48&80&\ldots&&&4&&17&18&\ldots&&&4&&11&17\cr
&&&\omit&&&&&&&&\omit&&&&&&5&&16\cr
}}$$
\bye
Since $R↓∞=\cup R↓i$, $qR↓∞q'$ iff $(\exists x)(q\delta↓x\in F∧q'\delta↓x\in\bar{F})$,
$q↓1\not\equiv q↓2$ iff $(q↓1R↓∞q↓2∨q↓2R↓∞q↓1)$, and the equivalence
relation~$R↓≡$ on states is $\overline{R↓∞\vphantom{↑1}}∧\overline{R↓∞↑{-1}}$.
(Alternatively, by letting $R↓0=F\times \overline{F}\cup \overline{F}\times F$,
we would have $R↓≡=\overline{R}↓∞$.
\bye
Transition functions are $\hbox{increment}(x)=x+1$,
$\hbox{decrement}(x)=x\dminus 1$. The test is $\hbox{zero}(x)≡(x=0)$.
\def\dminus{\mathrel{\vbox{\lineskip1pt\baselineskip0pt
\halign{\ctr{$##$}\cr
.\cr-\cr}}}}
Transition functions are $\hbox{increment}(x)=x+1$,
$\hbox{decrement}(x)=x\dminus 1$. The test is $\hbox{zero}(x)≡(x=0)$.
\def\tmo{\hbox{$\vcenter{\hbox{\tt .}\vskip-8pt\hbox{\tt -}}$}} %. over -
\halign{\qq\qq\lft{#}\q&\lft{#}\cr
{\tt C:=C\tmo 1}&Exercise for the reader\cr
{\tt C:=C$\!$\tmo$\!$1}&Exercise for the reader\cr
{\tt C:=C-1}&Exercise for the reader\cr}
\bye